package map;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.cn/problems/subarray-sum-equals-k/?favorite=2cktkvj
 *
 前缀和概念引入：
 首先计算出数组的前缀和数组，前缀和数组 preSum 中，preSum[i] 表示原数组 nums 中从下标 0 到下标 i 的元素总和（包含 nums[i]）。
 通过前缀和，我们可以快速计算出原数组中任意一段连续子数组的和。例如，要计算子数组 nums[i:j]（i 到 j 区间，包含 i 和 j）的和，
 就可以用 preSum[j] - preSum[i - 1]（前提是 i > 0，若 i == 0，则子数组 nums[0:j] 的和就是 preSum[j]）。
 利用哈希表优化：
 我们使用一个哈希表来记录前缀和出现的次数。在遍历数组计算前缀和的过程中，每次得到一个前缀和 preSum[i]，我们去查找哈希表中是否存在 preSum[i] - k 的值（因为如果存在 preSum[i] - k，
 那就意味着从某个前面的位置到当前位置的子数组和为 k）。
 如果存在 preSum[i] - k，则把对应的出现次数累加到结果中。然后，将当前的前缀和 preSum[i] 以及其出现次数更新到哈希表中（如果 preSum[i]
 已经在哈希表中，就把其出现次数加 1；如果不存在，就初始化为 1 次）。
 */

public class _560_和为k的子数组 {

    public int subarraySum(int[] nums, int k) {
        int preSum = 0;
        int count = 0;

        Map<Integer, Integer> map = new HashMap<>();
        // 初始化前缀和为0出现1次，用于处理从下标0开始的子数组情况
        map.put(0,1);

        for (int i = 0; i < nums.length; i++) {
            preSum += nums[i];

            if (map.containsKey(preSum - k)) {
                count += map.get(preSum - k);
            }

            map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }

        return count;
    }

}
